// greedy alg.
// init ratings all elements with 1.
// 分解为两条规则：
// 左规则：从左往右遍历，遇到ratings[i]>ratings[i-1]
// 右规则：从右往左遍历，同上
func candy(ratings []int) int {
	n := len(ratings)
	left := make([]int, n)
	right := make([]int, n)

	// filling with 1
	for i := 0; i < n; i++ {
		left[i] = 1
		right[i] = 1
	}

	for i := 1; i < n; i++ {
		if ratings[i] > ratings[i-1] {
			left[i] = left[i-1] + 1
		}
	}

	for i := n - 2; i >= 0; i-- {
		if ratings[i] > ratings[i+1] {
			right[i] = right[i+1] + 1
		}
	}

	sum := 0
	for i := 0; i < n; i++ {
		sum += max(left[i], right[i])
	}

	return sum
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}